# 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
# 实现 LRUCache 类：
# LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
# int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
# void put(int key, int value) 如果关键字已经存在，则变更其数据值；
# 如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，
# 它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
#
# 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
#
# 示例：
# 输入
# ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
# [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
# 输出
# [null, null, null, 1, null, -1, null, -1, 3, 4]
# 解释
# LRUCache lRUCache = new LRUCache(2);
# lRUCache.put(1, 1); // 缓存是 {1=1}
# lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
# lRUCache.get(1);    // 返回 1
# lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
# lRUCache.get(2);    // 返回 -1 (未找到)
# lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
# lRUCache.get(1);    // 返回 -1 (未找到)
# lRUCache.get(3);    // 返回 3
# lRUCache.get(4);    // 返回 4
#
# 提示：
# 1 <= capacity <= 3000
# 0 <= key <= 10000
# 0 <= value <= 105
# 最多调用 2 * 105 次 get 和 put

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.m = {}
        self.capacity = capacity
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key):
        if key not in self.m:
            return -1
        node = self.m[key]
        self._delete(node)
        self._add_to_head(node)
        return node.value

    def put(self, key, value):
        if key not in self.m:
            node = DLinkedNode(key, value)
            self.m[key] = node
            self._add_to_head(node)
        else:
            node = self.m[key]
            node.value = value
            self._delete(node)
            self._add_to_head(node)

        if len(self.m) > self.capacity:
            node = self.tail.prev
            self._delete(node)
            del self.m[node.key]

    def _add_to_head(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = self.head.next = node

    def _delete(self, node):
        node.prev.next, node.next.prev = node.next, node.prev
        node.prev = node.next = None
